-------
METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)
-------
Workshop on Metric embeddings, algorithms and hardness of approximation
January 17-21, 2011
-------
Jan 19, 16:00-17:00
Ryan O'Donnell (Carnegie Mellon U.)
Inapproximability: A How-To Guide 3
-------
In this mini-course, I will introduce the area of approximability of
optimization problems and then discuss the methods used to prove
inapproximability results. We will assume the hardness of Label-Cover
and Unique-Games - these problems will be discussed in other
mini-courses.
Key tools include the discrete Fourier transform and the notion of
"influences" for Boolean functions. As case studies, we will discuss
the Max-k-Coverage, Max-3Lin, and Max-Cut problems.
